1668B - Social Distance - CodeForces Solution


greedy math

Please click on ads to support us..

Python Code:




from __future__ import division, print_function

import os
import sys
import math
from io import BytesIO, IOBase
from heapq import heappush,heappop,heapify
from collections import defaultdict, Counter, deque

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")


def prod(a, mod=10 ** 9 + 7):
    ans = 1
    for each in a:
        ans = (ans * each) % mod
    return ans


def gcd(x, y):
    while y:
        x, y = y, x % y
    return x


def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y


def check_freq(x):
    freq = {}
    for c in set(x):
       freq[c] = x.count(c)
    return freq


def ii(): return int(input())
def si(): return input()
def mi(): return map(int, input().strip().split(" "))
def li(): return list(mi())
MAXX = 100000000


'''**************Solution is Here***********'''

def main():
    T = ii()
    for _ in range(T):
        n, k = li()
        soc = li()
        summ, maxx, minn = sum(soc), max(soc), min(soc)
        print("YES" if summ+maxx-minn+n <= k else "NO")


if __name__ == "__main__":
    main()


C++ Code:

#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
#define int long long
#define el '\n'
#define all(x) x.begin(),x.end()
#define get_bit(n,i) ((n>>i)& 1LL)
#define clr(v , d) memset(v, d , sizeof(v))
#define gmx(x , y) x = max(x ,y)
#define gmn(x , y) x = min(x , y)
#define f first
#define s second
const int N = 1e5 + 5,  mod = 1e9 + 7 , OO = 2 * 1e9;
const ll OOLL = 6 * 1e18;
const double pi = 3.1415926535897932384;
// #ifndef ONLINE_JUDGE
// #include "debug.h"
// #else
// #define debug(...)
// #endif
ll gcd(ll a, ll b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

void solve(){
	int n , m;
	cin >> n >> m;
	int ans = 0;
	vector < int > arr(n);
	for(auto &i : arr){
		cin >> i;
	}
	sort(all(arr) , greater < int >() );
	for(int i = 0;i < n - 1;++i){
		ans += arr[i] + 1;
	}
	int rem = m - (ans + 1);
	if(rem >= arr[0] and ((ans + arr.back() + 1) <= m)){
		cout << "YES\n";
	}else{
		cout << "NO\n";
	}

	//cout << (ans <= m ? "YES\n" : "NO\n");
}

int32_t main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(0);
    #ifndef ONLINE_JUDGE
     freopen("Error.in", "w", stderr);
    #endif
     int t = 1 ;
     cin >> t;
     while(t--){
        solve();
     }

    return 0;
}


Comments

Submit
0 Comments
More Questions

1605B - Reverse Sort
1607C - Minimum Extraction
1604B - XOR Specia-LIS-t
1606B - Update Files
1598B - Groups
1602B - Divine Array
1594B - Special Numbers
1614A - Divan and a Store
2085. Count Common Words With One Occurrence
2089. Find Target Indices After Sorting Array
2090. K Radius Subarray Averages
2091. Removing Minimum and Maximum From Array
6. Zigzag Conversion
1612B - Special Permutation
1481. Least Number of Unique Integers after K Removals
1035. Uncrossed Lines
328. Odd Even Linked List
1219. Path with Maximum Gold
1268. Search Suggestions System
841. Keys and Rooms
152. Maximum Product Subarray
337. House Robber III
869. Reordered Power of 2
1593C - Save More Mice
1217. Minimum Cost to Move Chips to The Same Position
347. Top K Frequent Elements
1503. Last Moment Before All Ants Fall Out of a Plank
430. Flatten a Multilevel Doubly Linked List
1290. Convert Binary Number in a Linked List to Integer
1525. Number of Good Ways to Split a String